package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.计数DP;

import java.util.*;
//将问题转换为01背包的体积恰好是j的模型。进行求解即可
class dp_11{
    static int mod = 1000000007;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int[] dp = new int[V + 1];
        //用grid保存每个到当前点的方案数，最后对所有满足条件的方案数进行求和即可
        int[] grid = new int[V + 1];
        Arrays.fill(dp,Integer.MIN_VALUE);
        dp[0] = 0;
        grid[0] = 1;
        for (int i = 0; i < N; i++){
            int v,w;
            v = in.nextInt();
            w = in.nextInt();
            for (int j = V; j >= v; j--){
                int maxv = Math.max(dp[j],dp[j - v] + w);
                int cnt = 0;
                if (maxv == dp[j]){
                    cnt += grid[j];
                }
                if (maxv == dp[j - v] + w){
                    cnt += grid[j - v];
                }
                grid[j] = cnt % mod;
                dp[j] = maxv;
            }
        }
        //先求出最优解，即最大值
        int res = 0;
        for (int i = 0; i <= V; i++){
            res = Math.max(res,dp[i]);
        }
        //如果dp[i] == res，则表示符合最优解，则把对应的方案数grid[i]累加即为答案
        int cnt = 0;
        for (int i = 0; i <= V; i++){
            if (res == dp[i]){
                cnt = (cnt + grid[i]) % mod;
            }
        }
        System.out.print(cnt);
    }
}
/*
有 N 件物品和一个容量是 V

的背包。每件物品只能使用一次。

第 i
件物品的体积是 vi，价值是 wi

。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 109+7

的结果。
输入格式

第一行两个整数，N，V

，用空格隔开，分别表示物品数量和背包容积。

接下来有 N
行，每行两个整数 vi,wi，用空格隔开，分别表示第 i

件物品的体积和价值。
输出格式

输出一个整数，表示 方案数 模 109+7

的结果。
数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 6

输出样例：

2

 */

